import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-06-28
 * Time: 15:08
 */
public class TestDemo {

    /**
     * 如果在一个数组中，只有一个数字出现了k次，其他数字都出现了m次，返回出现k次的数字，
     * 如果没有出现k次的数字，那么就返回-1
     */


    /**
     * 一个数组中有一种数字出现了k次,其他数字都出现了M次，其中M>1,K<M,找到出现K次的数字
     * @param array 数组
     * @param k k
     * @param m m
     * @return K次的数字
     */

    public static int onlyKTimes(int[] array,int k,int m){
        //对于每一个数字，我们都将其二进制加到同一个数组中
        int[] tmp = new int[32];
        for(int num:array){
            for(int i =0;i<32;++i){
                tmp[i] += ((num>>i)&1);
            }
        }
        //如果二进制的某一位%m!=0就证明这个位置上 我们要找的这个数字在这个位置上有1
        int ans =0;
        for(int i =0;i<32;++i){
            if((tmp[i]%m)!=0){
                ans |= (1<<i);
            }
        }
        return ans;
    }

    public static int RandomRange(int range){
        //产生【-100,100】之间的数字返回去
        return ((int)(Math.random()*range)+1) - ((int)(Math.random()*range)+1);
    }


    public static int[] RandomArray(int maxKinds,int range,int k,int m){
        int numKinds = ((int)(Math.random()*maxKinds))+2;//至少出现两种数字以上的数字
        //
        int Numbers = RandomRange(range);//产生0-maxRange范围的数字
        //这个KNumbers在数组中出现了k次
        int index =0;
        int[] array = new int[k+(numKinds-1)*m];
        for(;index<k;++index){
            array[index] = Numbers;
        }
        numKinds--;
        //再将mNumbers数字出现m次放进数组中并且与KNumbers不相同
        HashSet<Integer> set = new HashSet<>();
        set.add(Numbers);
        while(numKinds!=0){
            int currNum =0;
            do{
                 currNum = RandomRange(range);;
            }while(set.contains(currNum));
            numKinds--;
            set.add(currNum);
            for(int i=0;i<m;++i){
                array[index++] = currNum;
            }
        }
        for(int i =0;i<array.length;++i){
            //随机产生j位置与其i位置上的数字进行交换
            int j = (int) (Math.random()*array.length);//产生0-n-1的数字
            int tmp = array[i];
            array[i] = array[j];
            array[j] = tmp;
        }

        return array;
    }

    public static int test(int[] arr, int k, int m) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : arr) {
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }
        int ans = 0;
        for (int num : map.keySet()) {
            if (map.get(num) == k) {
                ans = num;
                break;
            }
        }
        return ans;
    }
    public static void main(String[] args) {
        int MaxKinds = 10;//出现的种数
        int testTimes = 10000;
        int max =9;
        int Range = 100;//产生【-100,100】之间的数字
        System.out.println("测试开始");
        for(int i =0;i<testTimes;++i){
            int a = ((int)(Math.random()*max))+1;//出现1-9之间的数字
            int b = ((int)(Math.random()*max))+1;//出现1-9之间的数字
            int k = Math.min(a,b);
            int m = Math.max(a,b);
            if(k==m){
                m++;//m一定比k大
            }
            int[] arr = RandomArray(MaxKinds,Range,k,m);
            int ans1 = onlyKTimes(arr,k,m);
            int ans2 = test(arr,k,m);
            if(ans1!=ans2){
               System.out.println("出错！！！");
            }
        }
        System.out.println("测试结束");
    }


    public static void main5(String[] args) {
        int[] array = {98,2,7,7,2,6,6,2,6,6,9,9,4,9,2,9,4,4,4,7,7,98};
        int k = 2;
        int m =4;
        int ans = onlyKTimes(array,k,m);
        System.out.println(ans);
    }

    /**
     * 一个数组中有两个数出现了奇数次，其他数字出现了偶数次，找到这两种数字并打印
     * @param array 默认数组
     * @return 返回数组
     */

    public static int[] twoNumOddTimes(int[] array){
        int eor = 0;
        for(int i =0;i<array.length;++i){
            eor^=array[i];
        }
        //此时eor=a^b
        //我们要先提取出一个数字，另外一个数字就可以根据异或提取出来
        //得到eor最右边的1
        int[] ans = new int[2];
        int rightOne = eor&(-eor);
        //对于每一个数字如果与rightOne在相同的位置出现了一我们就进行异或
        int tmp = 0;
        for(int i =0;i< array.length;++i){
            if((rightOne&(array[i]))!=0){
                tmp^=array[i];
            }
        }
        ans[0] =tmp;
        ans[1] =eor^tmp;

        return ans;
    }

    public static void main4(String[] args) {
        //一个数组中有两个数出现了奇数次，其他数字出现了偶数次，找到这两种数字并打印
        int[] array = {9,9,9,5,5,5,5,6,6,3,3,2,2,1,1,1,1,0,0,0,7,7,7,7,4,4};
        int[] ans = twoNumOddTimes(array);
        System.out.println(Arrays.toString(ans));
    }
    /**
     * 把一个int类型的数字提取出来最右侧的1
     * @param args 1
     */
    public static void main3(String[] args) {
        int num = 5;
        int ret = num&(-num);
        int ret1 = num&(~num+1);
        System.out.println("ret= "+ret +"\n"+"ret1="+ret1);
    }
    /**
     * 一个数组中有一种数字出现了奇数次，其他数字出现了偶数次，请打印这一种出现了奇数次的数字
     */
    public static int onlyOneTimes(int[] array){
        int ero = 0;
        for(int i =0;i<array.length;++i){
            ero^=array[i];
        }
        return ero;
    }

    public static void main2(String[] args) {
        int[] array = {1,1,1,1,8,8,9,6,6,3,3,4,4,7,7};
        int ans = onlyOneTimes(array);
        System.out.println(ans);
    }

    /**
     *  //不用任何额外临时变量，交换两个变量
     * @param array 1
     * @param i 0
     * @param j 1
     */


    public static void swap(int[] array,int i,int j){
        array[i] = array[i]^array[j];
        array[j] = array[i]^array[j];
        array[i] = array[i]^array[j];
    }
    public static void main1(String[] args) {
        int[] array ={5,10};
        swap(array,0,1);
        System.out.println(Arrays.toString(array));
    }

}
